<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <title>增量包算法</title>
</head>
<style>
  .container{
    width: 1000px;
    margin: 0 auto;
  }
  .item{
    margin-bottom: 20px;
    vertical-align: middle;
    float: none;
    clear: both;
  }
  .item label{
    width: 100px;
    float: left;
  }
  .item textarea{
    width: 60%;
    min-height: 100px;
  }
</style>
<script>
  //扫描法，复杂度为 n+m
  //生产增量包
  function makeChunk(s1,s2) {
    var n=s1.length,m=s2.length;//长度
    var n1=0,n2=0;//扫描点
    var chunkArr=[]
//开始扫描
    while (n1<n&&n2<m){
      //相等
      if(s1[n1]===s2[n2]){
        let nn1=n1+1;
        let nn2=n2+1;
        while (nn1<n&&nn2<m&&s1[nn1]===s2[nn2]){
          nn1++;
          nn2++;
        }
        chunkArr.push(['e',n1,nn1-n1])
        n1=nn1;
        n2=nn2;
      }else{
        let d1=0;
        let d2=0;
        if(n1+1<n){
          d2=1;
        }
        if(n2+1<m){
          d1=1;
        }
        if(d1===1&&d2===1){
          if(s1[n1+1]!==s2[n2+1]){
            while (n2+d1<m&&s1[n1]!==s2[n2+d1]){
              d1++;
            }
            while (n1+d2<n&&s1[n1+d2]!==s2[n2]){
              d2++;
            }
          }
        }

        if(d1===d2){
          //替换
          chunkArr.push(['r',s2.substr(n2,1)])
          n1=n1+1;
          n2=n2+1;
        }else if(d1<d2){
          //增加
          chunkArr.push(['a',s2.substr(n2,1)])
          n2=n2+1;
        }else{
          //删除
          // chunkArr.push(['d',n1,1,s1.substr(n1,1)])
          n1=n1+1;
        }
      }
      //超出的处理
      if(n1>=n&&n2<m){
        var i=s1.indexOf(s2[n2])
        if(i===-1){
          chunkArr.push(['a',s2.substr(n2,1)])
          n1=0;
          n2=n2+1;
        }else{
          n1=i;
        }
      }
    }
    //合并指令
    var minChunk=[]
    for(let i=0;i<chunkArr.length;i++){
      let arr=chunkArr[i];
      if(arr[0]==='r'||arr[0]==='a'){
        arr=['a',arr[1]]
      }
      var lastArr=minChunk[minChunk.length-1];
      if(arr[0]==='a'&&lastArr&&lastArr[0]==='a'){
        lastArr[1]=lastArr[1]+arr[1];
      }else{
        minChunk.push(arr)
      }
    }
    return minChunk;
  }

  function MinChunk(chunkArr,s1) {
    var minChunk=[]
    for(let i=0;i<chunkArr.length;i++){
      let arr=chunkArr[i];
      if(arr[0]==='e'&&arr[2]<String(arr[1]).length+6){
        arr=['a',s1.substr(arr[1],arr[2])]
      }
      var lastArr=minChunk[minChunk.length-1];
      if(arr[0]==='a'&&lastArr&&lastArr[0]==='a'){
        lastArr[1]=lastArr[1]+arr[1];
      }else{
        minChunk.push(arr)
      }
    }
    for(let i=0;i<minChunk.length;i++){
      let arr=minChunk[i];
      if(arr[0]==='a'){
        arr[0]=1;
      }else if(arr[0]==='e'){
        arr[0]=0;
      }
    }
    return minChunk;
  }
  //执行增量包
  function execChunk(s1,chunk){
    var ns=''
    for(let i=0;i<chunk.length;i++){
      const arr=chunk[i];
      if(arr[0]===0){
        ns=ns+s1.substr(arr[1],arr[2])
      }else if(arr[0]===1){
        ns=ns+arr[1]
      }
    }
    return ns
  }
</script>
<script>
  function s1makeChunk() {
    var s1=document.getElementById('s1').value;
    var s2=document.getElementById('s2').value;
    var chunk=makeChunk(s1,s2)
    var cstr=JSON.stringify(chunk)
    document.getElementById('chunk').value=cstr;

    var chunk2=MinChunk(chunk,s1)
    var cstr2=JSON.stringify(chunk2)
    document.getElementById('chunk2').value=cstr2
    return cstr
  }
  function s1execChunk() {
    var s1=document.getElementById('s1').value;
    var s2=document.getElementById('s2').value;
    var cstr=document.getElementById('chunk2').value
    if(!cstr){
      cstr=s1makeChunk();
    }
    var chunk=JSON.parse(cstr)
    var ns=execChunk(s1,chunk)
    document.getElementById('result').innerText='结果为'+(ns===s2);
    document.getElementById('ns').value=ns;
  }
</script>
<body>

<div class="container">
  <div class="item">
    增量包算法:时间复杂度 2*n ~ 2*n阶和 之间
  </div>
  <div class="item">
    <label>输入字符s1：</label> <textarea id="s1">ill:"071b136b",test:"acf98235",wlh_audit_ok:"0cfbdb93",wl</textarea>
  </div>
  <div class="item">
    <label>输入字符s2：</label> <textarea id='s2'>ill:"acf98235",test:"0cfbdb93",wlh_audit_ok:"0cfbdb93",wl</textarea>
  </div>
  <div class="item">
    <label>s1-->s2：</label> <textarea id='chunk'></textarea>
  </div>
  <div class="item">
    <label>指令压缩后</label> <textarea id='chunk2'></textarea><button onClick="s1makeChunk()">生产增量包：</button>
  </div>
  <div class="item">
    <label>结果：</label> <textarea id="ns"></textarea><button onClick="s1execChunk()">执行增量包：</button>
  </div>
  <div id="result"></div>
</div>

</body>
</html>
